package main.Q701_800;

import java.util.ArrayList;
import java.util.List;

public class Q721_730 {
    public static void main(String[] args) {
        System.out.println("Question721：");
        System.out.println("Question722：");
        System.out.println("Question723：");
        System.out.println("Question724：");
        System.out.println("Question725：分隔链表");
        System.out.println("Question726：");
        System.out.println("Question727：");
        System.out.println("Question728：");
        System.out.println("Question729：我的日程安排表Ⅰ");
        System.out.println("Question730：");
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Question725 {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode temp = head;
        int[] counts = new int[k];
        int i = 0;
        List<Integer> listNodes = new ArrayList<>();
        while (temp != null) {
            listNodes.add(temp.val);
            counts[i % k]++;
            i++;
            temp = temp.next;
        }
        ListNode[] result = new ListNode[k];
        i = 0;
        for (int j = 0; j < k; j++) {
            ListNode vir = new ListNode(), pre = vir;
            for (int n = 0; n < counts[j]; n++) {
                ListNode cur = new ListNode(listNodes.get(i++));
                pre.next = cur;
                pre = cur;
            }
            result[j] = vir.next;
        }
        return result;
    }
}

class Question729 {
    List<Integer> startList, endList;

    public Question729() {
        startList = new ArrayList<>();
        endList = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        if (startList.isEmpty()) {
            startList.add(start);
            endList.add(end);
            return true;
        } else {
            int lastStart = -1, lastEnd = -1, index = -1, i = 0;
            for (i = 0; i < startList.size(); i++) {
                int curStart = startList.get(i), curEnd = endList.get(i);//当前
                if (end <= curStart && start >= lastEnd) {//满足插入
                    index = i;
                    break;
                }
                lastEnd = curEnd;
                lastStart = curStart;
            }
            if (index == -1 && lastEnd <= start) index = startList.size();//判断插入末位
            if (index == -1) return false;
            else {
                startList.add(index, start);
                endList.add(index, end);
                return true;
            }
        }
    }
}